/**
 * 链式二叉树
 * @param <T>
 */
public class BinaryTree<T>{
    private Node<T> root;
    private final int maxNodes=100;
    /**
     * 创建一颗空树
     * @param x
     */
    public BinaryTree(T x)
    {
        this.root = new Node<T>(null);
    }

    /**
     * 在当前二叉树的parent结点中插入一个新的左子结点,
     * 已存在左子树，则将该左子树变成新左子树结点的左孩子树
     */
    public boolean insertLeft(T x,Node<T> parent)
    {
        if (parent == null)
        {
            return false;
        }
        Node<T> p = new Node<T>(x);
        if (parent.lChild==null)
        {
            parent.lChild=p;
        }
        else
        {
            p.lChild = parent.lChild;
            parent.lChild = p;
        }
        return true;
    }

    /**
     * 在当前二叉树的parent结点中插入一个新的右孩子结点，
     * 若已存在右子树，则将该右子树变成右子树变成新左子结点的左孩子树
     */
    public boolean insertRight(T x,Node<T> parent)
    {
        if (parent == null)
        {
            return false;
        }
        Node<T> p = new Node<T>(x);
        if (parent.rChild==null)
        {
            parent.rChild=p;
        }
        else
        {
            p.rChild = parent.rChild;
            parent.rChild = p;
        }
        return true;
    }
//    删除在当前二叉树的parent结点中的左子树
    public boolean deleteLeft(Node<T> parent)
    {
        if (parent == null)
        {
            return false;
        }
        else
        {
            parent.lChild=null;
            return true;
        }
    }
//    删除在当前二叉树的parent结点中的右子树
    public boolean deleteRight(Node<T> parent)
    {
        if (parent == null)
        {
            return false;
        }
        else
        {
            parent.rChild=null;
            return true;
        }
    }
    public void visit(T t){
        System.out.println(t);
    }

    /**
     * 先序遍历 DLR
     * @param node
     */
    public void preorder(Node<T> node)
    {
        if (node == null) return;
        else
        {
            visit(node.getData());
            preorder(node.lChild);
            preorder(node.rChild);
        }
    }

    /**
     * 中序遍历 LDR
     * @param node
     */
    public void inorder(Node<T> node)
    {
        if (node==null) return;
        else
        {
            inorder(node.lChild);
            visit(node.getData());
            inorder(node.rChild);
        }
    }

    public void postorder(Node<T> node)
    {
        if (node==null) return;
        else
        {
            postorder(node.lChild);
            postorder(node.rChild);
            visit(node.getData());
        }
    }

    /**
     * 逐层遍历二叉树
     */
    public void levelOrder()
    {

        Node<T>[]   queue = new Node[this.maxNodes];        //构造一个空队列
        int front,rear;                                     //队首指针、队尾指针
        if (this.root ==null) return;
        front = -1;                                         //队列暂时为空，队首指针不能向任何一个数组元素
        rear = 0;                                           //队列暂时为空，队尾指针指向第一个数组元素
        queue[rear] = this.root;                            //二叉树的根节点进队列
        while (front!=rear)
        {
            front++;
            /*访问队首结点的数据域*/
            visit(queue[front].getData());
            /*将队首结点的左孩子结点进队列*/
            if (queue[front].lChild!=null)
            {
                rear++;
                queue[rear]=queue[front].lChild;
            }
            /*将队首结点的右孩子结点进队列*/
            if (queue[front].rChild!=null)
            {
                rear++;
                queue[rear] = queue[front].rChild;
            }
        }
    }


//    求当前二叉树的高度
    public int getHeight(Node<T> parent)
    {
        int lh,rh,max;
        if (parent!=null)
        {
            lh = getHeight(parent.lChild);
            rh = getHeight(parent.rChild);
            max = lh>rh? lh:rh;
            return max+1;
        }
        else return 0;
    }
}

/**
 * 二叉树链存储的结点
 * @param <T>
 */
class Node<T>
{
    public Node<T> lChild;
    private T data;
    public Node<T> rChild;
    public Node()
    {
        data = null;
        lChild = null;
        rChild = null;
    }
    public Node(T x)
    {
        data = x;
        lChild = null;
        rChild = null;
    }
    public T getData()
    {
        return this.data;
    }
}
